package com.cty.twentyEighthDay;

import java.util.*;

/*
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 * */
public class Q_45 {
    // 力扣官方题解 广度优先搜索
    /*
     * 思路:
     *   使用广度优先搜索 遍历每层元素时将该层最后一个元素加入结果列表中
     *   时间复杂度O(n) 空间复杂度O(n)
     * */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                if (i == size - 1) {
                    ans.add(poll.val);
                }
            }
        }
        return ans;
    }

    // 力扣官方题解 深度优先算法
    /*
     * 思路:
     *   我们将遍历的顺序改为先根节点 然后右节点 左节点 将先序遍历的子节点顺序交换一下
     *   顺便在遍历的同时记录是否为本层的第一个元素 若是加入结果列表 如果不是则返回
     *   时间复杂度O(n) 空间复杂度O(n)(递归用到了栈)
     * */
    List<Integer> ans = new ArrayList<>();
    public List<Integer> rightSideView2(TreeNode root) {
        DFS(root,0);
        return ans;
    }

    public void DFS(TreeNode root,int depth) {
        if (root == null) {
            return;
        }
        if (depth == ans.size()) {
            ans.add(root.val);
        }
        depth++;
        DFS(root.right,depth);
        DFS(root.left,depth);
    }
}
